Kartki [A]

Limit pamięci: 32 MB

Jaś właśnie zaczął w szkole naukę dodawania liczb naturalnych. Mama Jasia wymyśliła dla niego grę, która ma mu pomóc w nauce. Na początku gry mama zapisuje na osobnych kartkach wszystkie liczby naturalne od do i ustawia kartki w rządku w kolejności zgodnej z numeracją. Zadaniem Jasia jest wielokrotne wykonywanie czynności, polegającej na zebraniu pierwszych kartek z rządka, zsumowaniu liczb zapisanych na tych kartkach, podarciu i wyrzuceniu tych kartek (poddawane są one następnie procesowi recyklingu) oraz zapisaniu otrzymanej sumy na nowej kartce i umieszczeniu jej na końcu rządka. Jeżeli w jakimś momencie zabawy jest mniej niż kartek w rządku, to Jaś się tym nie przejmuje i bierze do zsumowania wszystkie kartki z rządka.

Nowa zabawa bardzo wciągnęła Jasia, który co chwila prosi mamę o sprawdzenie, czy nie pomylił się w wykonywaniu kolejnych sumowań. Co więcej, Jasiowi gra zaczęła wychodzić coraz lepiej, więc powoli próbuje swoich sił dla bardzo dużych wartości i . Ponieważ mama Jasia przestała nadążać za wykonywanymi przez niego dodawaniami bardzo dużych liczb, poprosiła Cię o napisanie programu, który zamiast niej będzie weryfikował postępy Jasia.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia liczby , oraz ,
• wyznaczy jaka liczba powinna zostać zapisana na kartce przez Jasia w -tym ruchu gry,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę zapytań do programu. Kolejnych wierszy zawiera po trzy liczby całkowite , oraz (), pooddzielane pojedynczymi odstępami i oznaczające zapytanie o liczbę, którą Jaś powinien zapisać na kartce w -tym ruchu gry o parametrach oraz .

Wyjście

Wyjście powinno składać się z wierszy. -ty wiersz powinien zawierać jedną liczbę naturalną, będącą odpowiedzią na -te zapytanie z wejścia.

Przykład

6
6 2 1
6 2 2
6 2 3
6 2 4
6 2 5
6 2 6

3
7
11
10
21
21

Autor zadania: Jakub Radoszewski.